﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <sstream>
#include <cstring>
using namespace std;

// 01背包优化算法
//#include <iostream>
//#include <vector>
//#include <cstring>
//using namespace std;
//
//int main()
//{
//    int n = 0, V = 0;
//    cin >> n >> V;
//    vector<int> v(n + 1);
//    vector<int> w(n + 1);
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> v[i] >> w[i];
//    }
//
//    vector<int> dp1(V + 1);
//    vector<int> dp2(V + 1);
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = V; j >= 1; j--)
//        {
//            if (j - v[i] >= 0) dp1[j] = max(dp1[j], dp1[j - v[i]] + w[i]);
//        }
//
//    }
//    cout << dp1[V] << endl;
//
//    for (int j = 1; j <= V; j++) dp2[j] = -1;
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = V; j >= 1; j--)
//        {
//            if (j - v[i] >= 0 && dp2[j - v[i]] != -1)
//            {
//                dp2[j] = max(dp2[j], dp2[j - v[i]] + w[i]);
//            }
//        }
//    }
//    cout << (dp2[V] == -1 ? 0 : dp2[V]) << endl;
//    return 0;
//}


//class Solution {
//public:
//    bool canPartition(vector<int>& nums) {
//        int n = nums.size();
//        int sum = 0;
//        for (int i = 0; i < n; i++) sum += nums[i];
//        if (sum % 2 != 0) return false;
//        vector<vector<bool>> dp(n + 1, vector<bool>(sum / 2 + 1));
//
//        for (int i = 0; i <= n; i++) dp[i][0] = true;
//
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = 1; j <= sum / 2; j++)
//            {
//                dp[i][j] = dp[i - 1][j];
//                if (j >= nums[i - 1]) dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
//            }
//        }
//        return dp[n][sum / 2];
//    }
//};